home *** CD-ROM | disk | FTP | other *** search
/ Chip 1996 April / CHIP 1996 aprilis (CD06).zip / CHIP_CD06.ISO / hypertxt.arj / 92 / STRING.CD < prev    next >
Text File  |  1995-09-14  |  5KB  |  128 lines
  1.       @VStringek összehasonlítása@N
  2.  
  3.           Programok az olvasótól az olvasóhoz -- ennek a  mottónak
  4.       a szellemében  választjuk ki  hónapról-hónapra a  beérkezett
  5.       küldeményekbôl  a hasznos  programlistákat. Sajnos  egyelôre
  6.       még csak a CHIP német kiadásának szerkesztôségébe beérkezett
  7.       levelek  közül  válogathatunk, de  várjuk  a magyar  olvasók
  8.       leveleit is.
  9.           Ha egy  adathalmazban --  például egy  címállományban --
  10.       egy  bizonyos  szót  meg akarunk  találni,  akkor  a hibásan
  11.       rögzített adatok --  ha mondjuk a  ""Molnár"-t ""Nolnár"-nak
  12.       írták -- miatt a keresés sokszor eredménytelen. Kiutat kínál
  13.       e helyzetbôl  az itt  közölt HASONLO  Turbo Pascal  függvény
  14.       (lásd  a  mellékelt listát).  Két  string összehasonlítására
  15.       szolgál, és egy olyan értéket ad meg, amely azt jelzi,  hogy
  16.       a két  string mennyire  hasonlít egymáshoz.  Ha megegyeznek,
  17.       akkor  az  érték  0,  egyébként  minden  eltérésnél   1-gyel
  18.       növekszik az érték (túl sok,  túl kevés vagy hibás a  betû).
  19.       Például  a  következô  stringek  esetén  ezek  az eredmények
  20.       adódnak:
  21.           hasonlo('Computer','Computer') = 0
  22.           hasonlo('Computer','Cmputeer') = 2
  23.           hasonlo('Computer','Kombute') = 3
  24.           hasonlo('Computer','ootper') = 4
  25.           Mint  látható,  a  meglehetôsen  hibás  stringek  is még
  26.       viszonylag  kis  értéket  szolgáltatnak,  így  például  1-es
  27.       értékû hasonlóság  esetén a  példabeli Nollár  urat még  meg
  28.       lehetne  találni.  Ezt   a  rutint  szinte   megérintette  a
  29.       mesterséges intelligencia fuvallata...
  30.           A  megvalósítás  alapját   lényegében  a  Turbo   Pascal
  31.       rekurziós   képessége   adja.   Ha   a   stringek  különbözô
  32.       hosszúságúak,  akkor  a  rövidebb  minden  lehetséges  módon
  33.       kiegészül  #0-val,  s ennek  során  mindig végrehajtódik  az
  34.       összehasonlítás,   miközben  feltételezzük,   hogy  azok   a
  35.       kombinációk  szolgáltatják  a  legnagyobb  valószínûséggel a
  36.       keresett  eredményt,  amelyeknél  a  legnagyobb valószínûség
  37.       megállapításra  kerül.  Azért #0-val  történik  a feltöltés,
  38.       mert  ez az  érték a  Turbo Pascal  programokban  közönséges
  39.       esetben nem fordul elô, s ezért mindig az  egyenlôtlenségnek
  40.       megfelelô értéket adja.
  41.           Különleges problémát jelent összehasonlításkor, ha a két
  42.       string el  van tolva  egymáshoz képest  (például Computer és
  43.       omputero),   hiszen  itt   a  byte-onkénti   összehasonlítás
  44.       semmiféle  hasonlóságot  nem  találna.  A  következô eljárás
  45.       segít  ilyenkor,  amely felismeri  mindkét  irányban az  egy
  46.       hellyel  való   eltolódásokat:  egymásután   három  lépésben
  47.       töröljük azokat az azonos karaktereket, amelyek ugyanazon  a
  48.       helyen  állnak  vagy  egy hellyel  jobbra  illetve  balra el
  49.       vannak tolva.
  50.           A     ("computer","cmpllute")     füzérpárból    elôször
  51.       ("omputer","mpllute") lesz, majd ("outer","llute") és  végül
  52.       ("or","ll").  A  hasonlóság  2+2=4.  Az  elsô  összeadandó a
  53.       megmaradó betûk számának felel  meg, míg a második  azt adja
  54.       meg, hogy hány átlós összehasonlítás során talált a  program
  55.       megfelelést. A törlések  sorrendjének csak néhány  speciális
  56.       esetben van olyan hatása, hogy az eredmények kissé  eltérnek
  57.       egymástól.
  58.           Végül  néhány szó  a számítás  idejérôl: ha  a  stringek
  59.       hossza  erôsen  eltér,  akkor  a  #0-val  való   feltöltések
  60.       lehetôségének  nagy  száma miatt  a  számítási idô  igencsak
  61.       megnô, ezért ezt a mûveletet csak viszonylag kis különbségek
  62.       (öt karakternél kevesebb) esetén ajánlatos használni.
  63.  
  64.       @KFrank Langlotz@N
  65.  
  66.  
  67.       @V1.lista@N
  68.  
  69. program hasonlo_teszt;
  70.  
  71. function hasonlo(a,b:string):byte;
  72. var i,ered1,ered2:byte;
  73.     csere,bcopy:string;
  74.     valtozas:boolean;
  75. begin
  76.   ered1:=255;
  77.   if length(a)<length(b) then begin
  78.     csere:=a;
  79.     a:=b;
  80.     b:=csere;
  81.   end;
  82.   if length(a)>length(b) then
  83.     for i:=1 to length(a) do begin
  84.       bcopy:=b;
  85.       insert(#0,bcopy,i);
  86.       ered2:=hasonlo(a,bcopy);
  87.       if ered2<ered1 then ered1:=ered2;
  88.     end
  89.   else begin
  90.     ered2:=0;
  91.     i:=1;
  92.     while i<=length(a) do if a[i]=b[i] then begin
  93.       delete(a,i,1);
  94.       delete(b,i,1);
  95.     end else i:=i+1;
  96.     i:=2;
  97.     valtozas:=false;
  98.     while i<=length(a) do if a[i]=b[i-1] then begin
  99.       delete(a,i,1);
  100.       delete(b,i-1,1);
  101.       valtozas:=true;
  102.     end else i:=i+1;
  103.     if valtozas then ered2:=ered2+1;
  104.     i:=2;
  105.     valtozas:=false;
  106.     while i<=length(b) do if a[i-1]=b[i] then begin
  107.       delete(a,i-1,1);
  108.       delete(b,i,1);
  109.       valtozas:=true;
  110.     end else i:=i+1;
  111.     if valtozas then ered2:=ered2+1;
  112.     ered2:=ered2+length(a);
  113.     if ered2<ered1 then ered1:=ered2;
  114.   end;
  115.   hasonlo:=ered1;
  116. end;
  117.  
  118. begin
  119.   writeln;
  120.   writeln('"Computer","Computer"=',hasonlo('Computer','Computer'));
  121.   writeln('"Computer","Cmputeer"=',hasonlo('Computer','Cmputeer'));
  122.   writeln('"Computer","Kombute"=',hasonlo('Computer','Kombute'));
  123.   writeln('"Computer","ootper"=',hasonlo('Computer','ootper'));
  124.   writeln('"Computer","Cmpteraa"=',hasonlo('Computer','Cmpteraa'));
  125.   writeln('"Computer","Coomputr"=',hasonlo('Computer','Coomputr'));
  126.   writeln('"Computer","Compuuteer"=',hasonlo('Computer','Compuuteer'));
  127. end.
  128.